package com.huawei;

import java.util.Scanner;

/**
 * Created by Z-hong on 2024/7/3.
 */

public class HJ16 {
    public static class Product {
        public int content;
        public int[] arr;
        public Product(int content,int[] arr){
            this.content=content;
            this.arr=arr.clone();;
        }
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[][] arr=new int[m+1][4];
        for(int i=1;i<m+1;i++){
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
            arr[i][2]=sc.nextInt();
            arr[i][3]=arr[i][0]*arr[i][1];
        }

        Product[][] products=new Product[m+1][n+1];

        for(int i=0;i<=n;i++){
            products[0][i]=new Product(0,new int[m+1]);
        }

        for(int i=1;i<=m;i++){
            for(int j =0;j<=n;j++){
                //判断要加的i
                int remain = j-arr[i][0];

                //余数小于j值 && 余数相加满意度比当前的大 && 这是主键或者是有主键的附件
                if(remain<=j&&products[i-1][j-remain].content+arr[i][3]>products[i-1][j].content && !(arr[i][2]!=0&&products[i-1][j-remain].arr[i]!=1)){
                            int current=products[i-1][j-remain].content+arr[i][3];
                            //当前的满意度相加的大
                            Product p=new Product(current,products[i-1][j-remain].arr);
                            p.arr[i]=1;
                            products[i][j]=p;
                    }
                  else{
                        Product p=new Product(products[i-1][j].content,products[i-1][j].arr);
                        products[i][j]=p;
                    }


            }
        }
        System.out.println(products[m][n].content);
    }

}
